package class07;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: Code05_路径和收集路径
 * @Author: WangWenpeng
 * https://leetcode.com/problems/path-sum-ii
 */
public class Code05_路径和收集路径 {

    //收集符合的路径
    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        ArrayList<Integer> path = new ArrayList<>();
        process(root, path, 0, sum, ans);
        return ans;
    }

    public static void process(TreeNode x, List<Integer> path, int preSum, int sum, List<List<Integer>> ans) {
        if (x.left == null && x.right == null) {
            if (preSum + x.val == sum) {
                path.add(x.val);
                ans.add(copy(path));
                path.remove(path.size() - 1);
            }
            return;
        }
        // x 非叶节点
        path.add(x.val);
        preSum += x.val;
        if (x.left != null) {
            process(x.left, path, preSum, sum, ans);
        }
        if (x.right != null) {
            process(x.right, path, preSum, sum, ans);
        }
        path.remove(path.size() - 1);
    }

    public static List<Integer> copy(List<Integer> path) {
        List<Integer> ans = new ArrayList<>();
        for (Integer num : path) {
            ans.add(num);
        }
        return ans;
    }

    public static void main(String[] args) {
        TreeNode n41 = new TreeNode(7);
        TreeNode n42 = new TreeNode(2);
        TreeNode n43 = new TreeNode(5);
        TreeNode n44 = new TreeNode(1);
        TreeNode n31 = new TreeNode(11, n41, n42);
        TreeNode n32 = new TreeNode(13);
        TreeNode n33 = new TreeNode(4, n43, n44);
        TreeNode n21 = new TreeNode(4, n31, null);
        TreeNode n22 = new TreeNode(8, n32, n33);
        TreeNode n11 = new TreeNode(5, n21, n22);

        List<List<Integer>> lists = pathSum(n11, 22);
        System.out.println(lists);
    }
}
